1. Field of the Invention
The invention generally relates to a motion vector detector for use in a motion-compensated video coder and, more particularly, to a motion vector detecting method and system suited for software implementation for providing relatively high-precision motion vectors at a passable speed.
2. Description of the Prior Art
With an increase of systems using digital video signals, various code compression schemes have been proposed to reduce the data quantities of digital video signals used in such systems. Among others, MPEG (Moving Picture Experts Group) 1 and 2 coding are well-known and widely used for video signals used in computers. In these systems, video data are compressed through a combination of a reduction of spatial redundancy in a frame by means of DCT (discrete cosine transform) and a reduction of temporal redundancy between frames by means of the motion compensation. (For further details of MPEG 1, see ISO/IEC 11172—2, “Information technology—Coding of moving pictures and associated audio for digital storage media at up to about 1.5 M bit/s—Part2: Video.” Also, for MPEG 2, see ISO/IEC 13818—2, “Information technology-Generic coding of moving pictures and associated audio information—Part2: Video.”)
A reduction in spatial redundancy in coded video frames is achieved by motion-compensated coding. In motion-compensated coding, an object block 102 of a current frame 101 being coded is coded by searching a search range 103 defined around the corresponding block 104 in a past frame 105 for a block having the maximum correlation with the object block, i.e., a maximum correlation block 106; calculating a motion vector 107 from the corresponding block 104 to the detected maximum correlation block 106 and a block of difference data between the object block 102 and the maximum correlation block 106 as shown in FIG. 1; and coding the vector and the block of difference data. In MPEG system, the detection of motion vector is performed for each macroblock, i.e., by a unit of 2×2 blocks.
The calculations in the motion compensation account for a considerable portion of the calculations in the coding process. If a motion compensated video coder is to be implemented by software, the amount of calculations of the case where the search range is fully searched calculating the entire block of data in each matching will become impractically large.
For this reason, there have been proposed various speed-up algorithms. FIG. 2 illustrates three of such algorithms.
In algorithm (a), the number of matching operations is reduced by half by executing a matching operation every two bits in a search range 103a instead of conducting a full search. However, the steps (precision) of the motion vectors are also halved.
In algorithm (b), searching a full search range 103b with sampled data from the object block 102b reduces the amount of data in a matching operation. Though the steps of the motion vectors are the same as in the case of an ordinary full search, the reliability of the steps lowers.
In algorithm (c), searches are made not in a constant interval like every two bits but in a variable interval. A range 103c is first searched in a larger interval for a representative matching point and then only the neighborhood of the matching point is searched in a decreasing interval for a motion vector.
Various combinations of above-mentioned algorithms are possible. However, in the above-mentioned speed-up algorithms, the higher the detecting speed becomes, the lower the precision of detected motion vectors becomes, causing a lower picture quality. This is because each of the pixels in a noncompressed picture has a same weight, i.e., image information is homogeneously distributed in the pixels. Accordingly, it is impossible to reduce the amount of calculations by reducing the pixels to be used in the motion vector detection without sacrificing the precision of detected motion vectors and accordingly the picture quality as long as moving vectors are detected directly from noncompressed moving pictures.
By the way, as a compressive coding scheme, there is also a DV standard, which is a coding scheme for digital video devices such as digital video cameras etc. The DV standard is published as “Specification of Consumer-Use Digital VDRs,” (HD Digital VCR Conference, 1996). In this scheme, compression of image data is achieved by a reduction in spatial redundancy within a frame by DCTing each of the blocks.
The amount of code data per frame compressed by the DV scheme reaches six times that of code data compressed by a standard MPEG 2 scheme. From this viewpoint, MPEG coded data is more suitable for transmission of a video signal through a network such as PSTN (public switched telephone network). However, the frames of DV data are advantageously independent from one another, which facilitates video editing through frame-based cut and paste. Of course, DV data yields pictures of much the better quality for its plenty of codes.
For this reason, our group including the inventors has developed and put to practical use a system which edits moving pictures in a DV format taken in from a digital video camera and converts the format of edited moving pictures into an MPEG format for distribution to PC (personal computer) terminals. In such a system, video data in a DV format is decoded into uncompressed video data; and the uncompressed video data is compressed and coded in the MPEG format. However, if such DV-to-MPEG converter is to be implemented by software with degradation in picture quality held down, a conventional motion vector detecting system requires too much computation.
It is therefore an object of the invention to provide a system and method for detecting a motion vector with a high precision at a high speed from orthogonally transformed moving pictures.
For the purpose of future implementation of a real-time software DV-to-MPEG converter, the speed of motion vector detection has to be further raised.
It is another object of the invention to provide a method and system for use in combination with other higher-precision motion vector detector for detecting a motion vector with a rough precision at a speed of the order of a thirtieth.
Though the above-mentioned objects fails to deal with noncompressed moving pictures, we have succeeded in expanding the principle used in solving the above object to noncompressed or ordinary moving pictures.
It is further object of the invention to provide a method and system for detecting a motion vector with a high precision at a high speed from ordinary moving pictures.